package 单周赛.history;

import util.TreeNode;

/**
 *
 */
public class 第292场单周赛 {

    public static void main(String[] args) {

        System.out.println(largestGoodInteger("6777133339"));

        TreeNode treeNode = new TreeNode(4);
        TreeNode node8 = new TreeNode(8);
        TreeNode node5 = new TreeNode(5);
        TreeNode node0 = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node6 = new TreeNode(6);
        treeNode.left = node8;
        treeNode.right = node5;
        node8.left = node0;
        node8.right = node1;
        node5.right = node6;
        System.out.println(new 第292场单周赛().averageOfSubtree(treeNode));
    }


    /**
     * 双指针+模拟
     *
     * @param num
     * @return
     */
    public static String largestGoodInteger(String num) {
        String ans = "";
        int left = 0;
        while (left < num.length()) {
            int right = left + 1;
            while (right < num.length() && num.charAt(right) == num.charAt(left)) right++;
            if (right - left >= 3) {
                if (ans.equals("")) {
                    ans = num.substring(left, left + 3);
                } else if (num.charAt(left) > ans.charAt(0)) {
                    ans = num.substring(left, left + 3);

                }
            }
            left = right;
        }
        return ans;
    }

    /**
     * 用一个数组来存储当前节点，及其子节点的总和和个数
     *
     * @param root
     * @return
     */
    public int averageOfSubtree(TreeNode root) {
        Count count = new Count();
        search(root, count);
        return count.val;
    }

    public int[] search(TreeNode node, Count count) {
        int[] avg = new int[2];
        if (node == null) {
            return avg;
        }
        if (node.left != null) {
            int[] leftAvg = search(node.left, count);
            avg[0] += leftAvg[0];
            avg[1] += leftAvg[1];
        }
        if (node.right != null) {
            int[] rightAvg = search(node.right, count);
            avg[0] += rightAvg[0];
            avg[1] += rightAvg[1];
        }
        // 当前节点也要计算在内
        avg[0] += node.val;
        avg[1]++;
        if (avg[0] / avg[1] == node.val) count.val++;
        return avg;
    }

    class Count {
        private int val;
    }

}
